<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>爬楼梯算法解析 | 动态规划之美</title>
    <link href="https://cdn.staticfile.org/font-awesome/6.4.0/css/all.min.css" rel="stylesheet">
    <link href="https://cdn.staticfile.org/tailwindcss/2.2.19/tailwind.min.css" rel="stylesheet">
    <link href="https://fonts.googleapis.com/css2?family=Noto+Serif+SC:wght@400;500;600;700&family=Noto+Sans+SC:wght@300;400;500;700&display=swap" rel="stylesheet">
    <script src="https://cdn.jsdelivr.net/npm/mermaid@latest/dist/mermaid.min.js"></script>
    <style>
        body {
            font-family: 'Noto Sans SC', Tahoma, Arial, Roboto, "Droid Sans", "Helvetica Neue", "Droid Sans Fallback", "Heiti SC", "Hiragino Sans GB", Simsun, sans-serif;
            background-color: #f9f9f9;
            color: #333;
            line-height: 1.6;
        }
        .hero-gradient {
            background: linear-gradient(135deg, #667eea 0%, #764ba2 100%);
        }
        .code-block {
            background: #2d3748;
            border-left: 4px solid #667eea;
        }
        .card-hover {
            transition: all 0.3s ease;
        }
        .card-hover:hover {
            transform: translateY(-5px);
            box-shadow: 0 20px 25px -5px rgba(0, 0, 0, 0.1), 0 10px 10px -5px rgba(0, 0, 0, 0.04);
        }
        .step-card {
            border-radius: 12px;
            overflow: hidden;
        }
        .first-letter {
            font-size: 3.5rem;
            line-height: 1;
            float: left;
            margin-right: 0.5rem;
            margin-bottom: -0.5rem;
            font-weight: 700;
            color: #667eea;
        }
    </style>
</head>
<body class="min-h-screen">
    <!-- Hero Section -->
    <section class="hero-gradient text-white py-20 md:py-32 px-4">
        <div class="container mx-auto max-w-5xl">
            <div class="flex flex-col md:flex-row items-center">
                <div class="md:w-1/2 mb-10 md:mb-0">
                    <h1 class="text-4xl md:text-5xl font-bold mb-4 leading-tight">爬楼梯问题解析</h1>
                    <p class="text-xl md:text-2xl font-light mb-8 opacity-90">探索动态规划与斐波那契数列的优雅解法</p>
                    <div class="flex space-x-4">
                        <span class="px-4 py-2 bg-white bg-opacity-20 rounded-full text-sm font-medium">#动态规划</span>
                        <span class="px-4 py-2 bg-white bg-opacity-20 rounded-full text-sm font-medium">#算法精解</span>
                    </div>
                </div>
                <div class="md:w-1/2 flex justify-center">
                    <div class="w-64 h-64 bg-white bg-opacity-10 rounded-2xl flex items-center justify-center">
                        <i class="fas fa-chart-line text-6xl opacity-70"></i>
                    </div>
                </div>
            </div>
        </div>
    </section>

    <!-- Main Content -->
    <main class="container mx-auto max-w-5xl px-4 py-12">
        <!-- Problem Section -->
        <section class="mb-16">
            <div class="flex items-center mb-8">
                <div class="w-12 h-12 bg-indigo-100 rounded-full flex items-center justify-center mr-4">
                    <i class="fas fa-question text-indigo-600 text-xl"></i>
                </div>
                <h2 class="text-3xl font-bold text-gray-800">题目描述</h2>
            </div>
            
            <div class="bg-white rounded-xl shadow-md p-6 md:p-8 card-hover">
                <div class="flex items-start">
                    <div class="mr-4 text-indigo-500">
                        <i class="fas fa-stairs text-2xl"></i>
                    </div>
                    <div>
                        <p class="text-lg text-gray-700 mb-4">假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？</p>
                        <p class="text-gray-600">例如，爬到第 3 阶楼梯有 3 种方法：1+1+1、1+2、2+1。</p>
                    </div>
                </div>
            </div>
        </section>

        <!-- Key Concepts -->
        <section class="mb-16">
            <div class="flex items-center mb-8">
                <div class="w-12 h-12 bg-indigo-100 rounded-full flex items-center justify-center mr-4">
                    <i class="fas fa-lightbulb text-indigo-600 text-xl"></i>
                </div>
                <h2 class="text-3xl font-bold text-gray-800">核心考点与算法</h2>
            </div>
            
            <div class="grid md:grid-cols-2 gap-6">
                <div class="bg-white rounded-xl shadow-md p-6 card-hover">
                    <div class="flex items-center mb-4">
                        <div class="w-10 h-10 bg-blue-100 rounded-full flex items-center justify-center mr-3">
                            <i class="fas fa-project-diagram text-blue-600"></i>
                        </div>
                        <h3 class="text-xl font-bold text-gray-800">动态规划</h3>
                    </div>
                    <p class="text-gray-700">将问题分解为相互重叠的子问题，通过解决子问题来构建原问题的解，避免重复计算。</p>
                </div>
                
                <div class="bg-white rounded-xl shadow-md p-6 card-hover">
                    <div class="flex items-center mb-4">
                        <div class="w-10 h-10 bg-purple-100 rounded-full flex items-center justify-center mr-3">
                            <i class="fas fa-superscript text-purple-600"></i>
                        </div>
                        <h3 class="text-xl font-bold text-gray-800">斐波那契数列</h3>
                    </div>
                    <p class="text-gray-700">爬楼梯问题实质上是一个斐波那契数列问题，其中每个数都是前两个数的和。</p>
                </div>
            </div>
        </section>

        <!-- Solution Section -->
        <section class="mb-16">
            <div class="flex items-center mb-8">
                <div class="w-12 h-12 bg-indigo-100 rounded-full flex items-center justify-center mr-4">
                    <i class="fas fa-code text-indigo-600 text-xl"></i>
                </div>
                <h2 class="text-3xl font-bold text-gray-800">解题思路</h2>
            </div>
            
            <div class="bg-white rounded-xl shadow-md overflow-hidden mb-8">
                <div class="p-6 md:p-8">
                    <div class="flex items-start mb-2">
                        <span class="first-letter">解</span>
                        <div>
                            <p class="text-gray-700 mb-4">定义 dp[i] 为爬到第 i 阶的方法数，则 dp[i] = dp[i-1] + dp[i-2]，因为可以从 i-1 或 i-2 到达 i。</p>
                            <p class="text-gray-700">时间复杂度：O(n)，空间复杂度：O(n)；优化空间可至 O(1)。</p>
                        </div>
                    </div>
                </div>
                
                <div class="bg-gray-50 p-6 md:p-8 border-t">
                    <h3 class="text-xl font-bold text-gray-800 mb-4">分步解析</h3>
                    <div class="grid md:grid-cols-3 gap-4">
                        <div class="step-card bg-white p-4 shadow-sm border border-gray-100">
                            <div class="flex items-center mb-3">
                                <span class="w-8 h-8 bg-indigo-500 text-white rounded-full flex items-center justify-center mr-2 font-bold">1</span>
                                <h4 class="font-bold text-gray-800">确定状态</h4>
                            </div>
                            <p class="text-gray-600 text-sm">dp[i] 表示到达第i阶的方法数</p>
                        </div>
                        <div class="step-card bg-white p-4 shadow-sm border border-gray-100">
                            <div class="flex items-center mb-3">
                                <span class="w-8 h-8 bg-indigo-500 text-white rounded-full flex items-center justify-center mr-2 font-bold">2</span>
                                <h4 class="font-bold text-gray-800">状态转移</h4>
                            </div>
                            <p class="text-gray-600 text-sm">dp[i] = dp[i-1] + dp[i-2]</p>
                        </div>
                        <div class="step-card bg-white p-4 shadow-sm border border-gray-100">
                            <div class="flex items-center mb-3">
                                <span class="w-8 h-8 bg-indigo-500 text-white rounded-full flex items-center justify-center mr-2 font-bold">3</span>
                                <h4 class="font-bold text-gray-800">初始条件</h4>
                            </div>
                            <p class="text-gray-600 text-sm">dp[1] = 1, dp[2] = 2</p>
                        </div>
                    </div>
                </div>
            </div>
            
            <div class="bg-white rounded-xl shadow-md overflow-hidden">
                <div class="bg-gray-800 text-white px-6 py-3 flex items-center">
                    <i class="fab fa-java text-xl mr-3 text-red-400"></i>
                    <span class="font-mono">Java 实现</span>
                </div>
                <div class="code-block p-6 overflow-x-auto">
                    <pre class="text-gray-200 font-mono text-sm">
<code>public int climbStairs(int n) {
    // 处理基本情况
    if (n <= 2) {
        return n;
    }
    
    // 创建动态规划数组，dp[i]表示爬到第i阶的方法数
    int[] dp = new int[n + 1];
    
    // 初始化基本情况
    dp[1] = 1;
    dp[2] = 2;
    
    // 自底向上填充dp数组
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2]; // 当前阶梯的方法数等于前两个阶梯方法数之和
    }
    
    // 返回爬到第n阶的方法数
    return dp[n];
}</code></pre>
                </div>
            </div>
        </section>

        <!-- Visualization Section -->
        <section class="mb-16">
            <div class="flex items-center mb-8">
                <div class="w-12 h-12 bg-indigo-100 rounded-full flex items-center justify-center mr-4">
                    <i class="fas fa-chart-pie text-indigo-600 text-xl"></i>
                </div>
                <h2 class="text-3xl font-bold text-gray-800">可视化解析</h2>
            </div>
            
            <div class="bg-white rounded-xl shadow-md p-6 md:p-8">
                <div class="mermaid">
                    graph TD
                        A[爬楼梯问题] --> B[定义子问题]
                        A --> C[发现最优子结构]
                        B --> D[dp[i]: 到达第i阶的方法数]
                        C --> E[dp[i] = dp[i-1] + dp[i-2]]
                        D --> F[初始条件: dp[1]=1, dp[2]=2]
                        E --> G[自底向上计算]
                        G --> H[返回dp[n]]
                </div>
            </div>
        </section>

        <!-- Optimization Section -->
        <section>
            <div class="flex items-center mb-8">
                <div class="w-12 h-12 bg-indigo-100 rounded-full flex items-center justify-center mr-4">
                    <i class="fas fa-bolt text-indigo-600 text-xl"></i>
                </div>
                <h2 class="text-3xl font-bold text-gray-800">优化思路</h2>
            </div>
            
            <div class="bg-white rounded-xl shadow-md p-6 md:p-8 card-hover">
                <div class="flex items-start mb-4">
                    <div class="mr-4 text-green-500">
                        <i class="fas fa-rocket text-2xl"></i>
                    </div>
                    <div>
                        <h3 class="text-xl font-bold text-gray-800 mb-2">空间优化到 O(1)</h3>
                        <p class="text-gray-700">由于 dp[i] 只依赖于前两个状态，我们可以用两个变量代替整个数组，将空间复杂度从 O(n) 降到 O(1)。</p>
                    </div>
                </div>
                
                <div class="mt-6 bg-gray-50 p-4 rounded-lg">
                    <h4 class="font-bold text-gray-800 mb-3">优化后的 Java 实现</h4>
                    <div class="code-block p-4 overflow-x-auto">
                        <pre class="text-gray-200 font-mono text-sm">
<code>public int climbStairsOptimized(int n) {
    if (n <= 2) return n;
    
    int prev1 = 1;  // dp[i-2]
    int prev2 = 2;  // dp[i-1]
    
    for (int i = 3; i <= n; i++) {
        int current = prev1 + prev2;
        prev1 = prev2;
        prev2 = current;
    }
    
    return prev2;
}</code></pre>
                    </div>
                </div>
            </div>
        </section>
    </main>

    <script>
        mermaid.initialize({
            startOnLoad: true,
            theme: 'default',
            flowchart: {
                useMaxWidth: true,
                htmlLabels: true,
                curve: 'basis'
            }
        });
    </script>
</body>
</html>